A well known technique for digital data transformation is to employ the digital data to be transformed as an address to a look up table (LUT) or electronic memory storing a transformation of the digital data to be transformed. Each combination of bits specifies a single location in memory which stores the transformation of the data element corresponding to that combination of bits. LUTs are used in many types of applications such as in color image processing in color pre-press situations.
Memory volume requirements for LUTs are determined by the number of combinations of bits of the input data, as well as by the depth of representation. In color transformation applications, in which a color space may include 2.sup.24 colors, or more than 16 million colors, a memory having more than 16 million entries or cells may be required, as shown in prior art FIG. 1. This volume of memory is expensive. Also, loading and modification processes become extremely time consuming.
Techniques for reducing memory size are known. These techniques result in a reduction of transformation accuracy to a greater or lesser extent. One such technique, as illustrated in prior art FIG. 2, is to provide only a small number of memory cells corresponding to only a small fraction of the possible input values, such as only 4096 memory cells instead of providing more than 16 million memory cells. Output values for all remaining possible input values, to which no memory cell is assigned, are computed by interpolation or extrapolation based on the distances of an individual input value from the cell addresses which are closest to the individual input value.
A LUT in which the number of possible input values which have a memory cell assigned to them is only a small fraction of the total number of possible input values is also termed herein a "low resolution" LUT.
According to this technique, the majority of transformations are not derived directly from the LUT, since the majority of input values to be transformed do not address any of the memory cells of the LUT. Instead, transformed data for these input values is computed by interpolation from the contents of adjacent memory cells. The factor of gain in memory volume and in loading time is equal to the factor of loss of transformation resolution.
One disadvantage of this method is that LUTs are often employed to represent non-linear transformations in which output values whose addresses fall intermediate a plurality of LUT cells are not linear combinations of the contents of those LUT cells. For these transformations, the results of linear interpolation procedures are normally inaccurate. Furthermore, the inaccuracies introduced by the interpolation process are normally not uniform across the data space to be transformed, but vary thereacross.
For example, for some color spaces, the nonuniformity of the inaccuracies introduced by standard color transformation interpolation processes is such that dark colors are distorted because they are transformed with substantial inaccuracy. Colors which are distorted substantially when they are transformed by interpolation are believed to be colors for which the perception of the human eye is non-linear relative to the actual physical properties of the colors perceived.
U.S. Pat. Nos. 4,941,029 and 4,992,861, both to D'Errico, disclose a technique for reducing memory size which is described as causing relatively little reduction of transformation accuracy. D'Errico provides a method for employing a LUT for interpolation purposes in which an interpolation algorithm with special features is employed.
Published European Application 0366309 to IBM describes a color image quantization system in which color data representative of an input color space of a picture is loaded into a single LUT. The representative data is determined by repeated division of the input color space of the picture into K child-spaces, where K is the number of cells in the LUT. The order of division is dependent upon the distribution of original image pels within the existing child-spaces. Eventually, the distribution of pels within the child-spaces is nearly uniform, thereby maintaining image quality for images having a given distribution of pels within the input color space.
The criterion according to which the IBM method operates is an image-specific criterion whereby precedence is given to color subspaces which are densely populated with image pels. The method is not operative to give precedence to color subspaces in which the non-linearity of the color transformation is particularly pronounced.
Also, the LUT disclosed in the above-referenced IBM document is addressed by nominal index values assigned to each pel rather than by the actual color of each pel. Consequently, it is impossible to carry out a meaningful interpolation process.
The eventual set of child-spaces defined by the IBM method typically includes child-spaces of different sizes. For example, FIG. 5 of the above-referenced IBM document is a conceptual diagram of a divided color-space management list. As shown, the eventual set of child-spaces in FIG. 5 includes 7 child-spaces on level 1, 7 child-spaces on level 2 and 7 child-spaces on level 3. The size of the child-spaces on levels 1, 2 and 3 are 1/8, 1/(8.times.8) and 1/(8.times.8.times.8) respectively.